package leetcode_题库;

import java.util.*;

public class _567_字符串的排列 {
    public static void main(String[] args) {
        String s1 = "adc";
        String s2 = "dcda";

        System.err.println(checkInclusion(s1, s2));
    }

    public static boolean checkInclusion(String s1, String s2) {
        //记录m、n的长度
        int m = s1.length();
        int n = s2.length();

        if (m > n){
            //若待查询的字符串比被查询串长，肯定不会s2包含s1
            return false;
        }
        //滑动窗口不一定需要双指针，数组就是讨巧的办法
        //定义两数组，长度都是26（字符相减得到Ascii码的序列，就是int。'z'-'a'是a~z的距离25，再加1就是26）
        int[] arrM = new int[26];
        int[] arrN = new int['z'-'a' + 1];
        //先遍历到m
        for (int i = 0; i < m; i++) {
            //让两个数组arrM、arrN分别对应s1和s2，由于题干中s1和s2仅包含小写字母，所以都减去'a'，让它们下标介于0~25之间
            //比如第一个是a，那么arrM[0]对应值+1，第二个是z，那么arrM[25]对应值+1，第三个还是a，arrM[0]应该是2了
            arrM[s1.charAt(i) - 'a'] ++;
            arrN[s2.charAt(i) - 'a'] ++;
        }
        //有可能直接匹配了，所以调用Arrays.equals比较
        if (Arrays.equals(arrM,arrN)){
            return true;
        }
        //没匹配，开始滑动窗口，右边界是i，左边界其实就是i-m（保持窗口大小固定位m即可，在刚那个循环已经做到了）
        for (int i = m; i < n; i++) {
            //让第i-'a'个++
            arrN[s2.charAt(i) - 'a'] ++;
            //让第(i-m)-'a'个--，相当于讨巧的右移了左窗口
            arrN[s2.charAt(i - m) - 'a'] --;
            if (Arrays.equals(arrM,arrN)){
                //每次进行比较
                return true;
            }
        }
        //最后肯定没有匹配
        return false;
        /*

            > 2022/08/22 09:34:22
            解答成功:
                执行耗时:5 ms,击败了77.97% 的Java用户
                内存消耗:41.3 MB,击败了63.68% 的Java用户

         */
    }

    /**
     * 自己写的勾八算法，1614ms，击败5％，也算写出来了，毕竟也有7000ms+没超时的
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusionFuck(String s1, String s2) {
        //定义s1的指针
        int p1 = 0;
        //定义s2的指针
        int p2 = 0;
        //是否找到匹配的字符，若是则记忆为true
        boolean isMemory = false;
        //记忆第一个匹配的字符的位置（如果不能完全匹配，p2要恢复回记忆点的后一位，相当于左窗口右移）
        int p2Memory = 0;

        //让s1都被插入到哈希表
        HashMap<Character,Integer> map = new HashMap<>(s1.length());
        for (int i = 0; i < s1.length(); i++) {
            map.put(s1.charAt(i),map.getOrDefault(s1.charAt(i),0)+1);
        }

        //复制一份哈希表
        HashMap<Character,Integer> tempMap = (HashMap<Character, Integer>) map.clone();
        //若p2还没遍历完就继续
        while (p2 < s2.length()) {
            //获取p2的指针位置
            char key = s2.charAt(p2);
            //如果p1长度没有走满（没比较完），且在剩余map中依然有匹配
            if (p1 < s1.length() && tempMap.containsKey(key) && tempMap.get(key) > 0){
                //数量-1
                tempMap.put(key,tempMap.get(key) - 1);
                //p1右移
                p1++;
                if (!isMemory){
                    //如果没有记忆，这是第一个匹配点，记忆
                    p2Memory = p2;
                    isMemory = true;
                }
            }else{
                //遇到不匹配了，先看p1走完没，走完就说明前面那一段匹配了
                if (p1 == s1.length()){
                    return true;
                }
                //如果没有记忆点就不管，有记忆点就恢复并清除记忆（在结尾有p2++右移窗口，所以这里不需要右移）
                if (isMemory){
                    p2 = p2Memory;
                    isMemory = false;
                }
                //清空之前的map
                tempMap = (HashMap<Character, Integer>) map.clone();
                //恢复p1的位置
                p1 = 0;
            }
            //s2的窗口右移
            p2++;
        }
        //看p1走完没，走完就说明前面那一段匹配了，否则没匹配
        return p1 == s1.length();
    }
}
